# TODO: Handle create, delete, update
# TODO: Create Query objects from query methods

from enum import Enum, unique
from functools import cmp_to_key
from collections import OrderedDict, namedtuple, defaultdict
from threading import RLock
import operator
import copy
import time as time_mod
import functools


@unique
class Order(Enum):
    ASCENDING = 1
    DESCENDING = 2
    ANY = 3


INCOMPATIBLE = {
    "paginated": {"specific", "count", "ranged"},
    "count": {"specific", "ranged", "ordered_by"},
    "specific": {"ranged", "ordered_by", "filtered_by"},
}

STRICTLY_COMPATIBLE = {
    "create": set(),
    "delete": set(),
    "update": set(),
}

OPERATORS = {
    "==": operator.eq,
    "!=": operator.ne,
    "<": operator.lt,
    "<=": operator.le,
    ">": operator.gt,
    ">=": operator.ge,
}


def fields(*names, readonly=True):
    names = [
        name if isinstance(name, tuple) else (name, None) for name in names
    ]

    def decorator(cls):
        class NewClass(cls):
            def __init__(self, *args, **kwargs):
                for name, default in names:
                    try:
                        getattr(self, name)
                    except AttributeError:
                        value = default() if callable(default) else default
                        setattr(self, name, value)
                super().__init__(*args, **kwargs)
                if readonly:
                    setattr(self, "__readonly", True)

        def set_prop(name):
            @property
            def prop(self):
                return getattr(self, "__" + name)

            @prop.setter
            def prop(self, value):
                if getattr(self, "__readonly", False):
                    raise AttributeError("Cannot set read-only property.")
                setattr(self, "__" + name, value)
            setattr(NewClass, name, prop)

        if readonly:
            for name, _ in names:
                set_prop(name)

        NewClass.__name__ = cls.__name__
        NewClass.__qualname__ = cls.__qualname__
        NewClass.__doc__ = cls.__doc__
        return NewClass
    return decorator


def locked(attr="_lock"):
    def decorator(func):
        @functools.wraps(func)
        def result(self, *args, **kwargs):
            with getattr(self, attr):
                return func(self, *args, **kwargs)
        return result
    if callable(attr):
        func, attr = attr, "_lock"
        return decorator(func)
    return decorator


# TODO: Should copy methods from PublicQuery or a subclass
class ObjectManager:
    def __init__(self, model_db):
        self.database = model_db

    @property
    def id(self):
        return self.database.id


class ModelMeta(type):
    def __init__(self, name, bases, attrs):
        if self._base:
            self._base = False
            return
        if self.fields is super(self, self).fields:
            self.fields = []
        if self.inherit_fields:
            self.fields = list(super(self, self).fields) + list(self.fields)
        field_set = OrderedDict([("id", None)])
        field_set.update((f, None) for f in self.fields)
        field_set.pop("pk", None)
        self.fields = list(field_set)
        self.field_set = set(self.fields)


class Model(metaclass=ModelMeta):
    _base = True
    managers = {}
    Manager = ObjectManager
    inherit_fields = True
    fields = []
    field_set = set()

    def __init__(self, **kwargs):
        self.manager = None
        for field in self.fields:
            setattr(self, field, None)
        for key, value in kwargs.items():
            if key == "pk":
                key = "id"
            if key not in self.field_set:
                raise TypeError("'{}' is not a field.".format(key))
            setattr(self, key, value)

    @property
    def db_id(self):
        return self.manager.database.id

    @property
    def pk(self):
        return self.id

    @pk.setter
    def pk(self, value):
        self.id = value

    @classmethod
    def add_database(cls, model_db):
        db_id = model_db.id
        if db_id in cls.managers:
            raise ValueError(
                "Database with ID '{}' already exists.".format(db_id),
            )
        manager = cls.Manager(model_db)
        cls.managers[db_id] = manager

    def copy(self):
        return type(self)(**{f: getattr(self, f) for f in self.fields})

    @classmethod
    def objects(cls, db_id):
        try:
            return cls.managers[db_id]
        except KeyError as e:
            raise ValueError(
                "Database with ID '{}' does not exist.".format(db_id),
            ) from e

ALLOWED_MODELDB_OVERRIDES = {
    "model", "cache_timeout",
}


class ModelDBMeta(type):
    def __init__(self, name, bases, attrs):
        self.unbound_methods = list(getattr(self, "unbound_methods", []))
        for attr_name in attrs:
            if attr_name.startswith("__") and attr_name.endswith("__"):
                continue

            value = getattr(self, attr_name)
            if not (callable(value) and getattr(value, "_query", False)):
                if self._override or not hasattr(ModelDatabase, attr_name):
                    continue
                if attr_name in ALLOWED_MODELDB_OVERRIDES:
                    continue
                raise TypeError(
                    "Attribute '{}' overrides attribute in "
                    "ModelDatabase.".format(attr_name),
                )

            def raise_conflict(dec_name, conflicts):
                raise RuntimeError("Cannot use @{} with: {}".format(
                    dec_name, ", ".join("@" + name for name in conflicts),
                ))

            for key, others in INCOMPATIBLE.items():
                if not hasattr(value, "_" + key):
                    continue
                conflicts = value._decorators & others
                if conflicts:
                    raise_conflict(key, conflicts)

            for key, others in STRICTLY_COMPATIBLE.items():
                if not hasattr(value, "_" + key):
                    continue
                conflicts = value.decorators - others
                if conflicts:
                    raise_conflict(key, conflicts)

            self.unbound_methods.append(Method(value))
            setattr(self, attr_name, getattr(
                super(self, self), attr_name, None,
            ))

        if self._base:
            self._base = False
        if self._override:
            self._override = False
        elif self.model is None:
            raise TypeError("Database must specify a model.")

    def __call__(self, *args, **kwargs):
        obj = self.__new__(self, *args, **kwargs)
        obj.__init__(*args, **kwargs)
        if not getattr(obj, "_base_init_called", False):
            raise RuntimeError(
                "Classes derived from ModelDatabase must call "
                "the super constructor.",
            )
        return obj


class ModelDatabase(metaclass=ModelDBMeta):
    _base = True
    _override = True

    model = None
    cache_timeout = 600

    # Instance attributes that usually shouldn't be shadowed/overridden
    id = None
    cache = None

    def __init__(self, id):
        self.id = id
        self.cache = {}
        self._lock = RLock()
        self._base_init_called = True

    def register(self):
        self.model.add_database(self)

    @property
    def methods(self):
        return [m.bind(self) for m in self.unbound_methods]

    @locked
    def get_cached(self, params):
        self.clean_cache()
        obj = self.cache.get(params)
        if obj is None:
            return None
        (time, result) = obj
        return result.objects

    @locked
    def clean_cache(self):
        current_time = time_mod.monotonic()
        remove_keys = set()
        for key, (time, result) in self.cache.items():
            if current_time - time > self.cache_timeout:
                remove_keys.add(key)
        for key in remove_keys:
            del self.cache[key]

    @locked
    def add_to_cache(self, cached_result):
        params = cached_result.params
        self.cache.pop(params, None)
        self.cache[params] = (time_mod.monotonic(), cached_result)


@fields(
    "func", "paginate", "order", "filters", "count", "specific", "range",
    "create", "update", "delete")
class Method:
    def __init__(self, func):
        self.func = func
        self.paginate = getattr(func, "_paginated", PaginationDescriptor())
        self.order = getattr(func, "_ordered_by", OrderDescriptor())
        self.filters = getattr(func, "_filtered_by", FilterDescriptor())
        self.count = getattr(func, "_count", CountDescriptor())
        self.specific = getattr(func, "_specific", SpecificDescriptor())
        self.range = getattr(func, "_ranged", RangeDescriptor())
        self.create = getattr(func, "_create", CreateDescriptor())
        self.update = getattr(func, "_update", UpdateDescriptor())
        self.delete = getattr(func, "_delete", DeleteDescriptor())

    def __call__(self, *args, **kwargs):
        result = self.func(*args, **kwargs)
        if self.specific:
            return [result]
        return result

    def bind(self, obj):
        result = copy.copy(self)
        setattr(result, "__func", self.func.__get__(obj))
        return result


@fields(
    "method", "num_missing_filters", "correct_order", "correct_range",
    "usable_range", "usable_specific", "usable_count")
class MethodStats:
    def __init__(self, method, *, num_missing_filters, correct_order,
                 correct_range, usable_range, usable_specific, usable_count):
        self.method = method
        self.num_missing_filters = num_missing_filters
        self.correct_order = correct_order
        self.correct_range = correct_range
        self.usable_range = usable_range
        self.usable_specific = usable_specific
        self.usable_count = usable_count


@fields("value")
class Descriptor:
    def __bool__(self):
        return bool(self.value)


@fields(("dict", dict))
class DictDescriptor(Descriptor):
    def __len__(self):
        return len(self.dict)

    def __getitem__(self, key):
        return self.dict[key]

    def __iter__(self):
        return iter(self.dict)

    def __contains__(self, item):
        return item in self.dict

    def keys(self):
        return self.dict.keys()

    def values(self):
        return self.dict.values()

    def items(self):
        return self.dict.items()

    def get(self, *args, **kwargs):
        return self.dict.get(*args, **kwargs)


@fields("items_per_page", ("relative", False), ("always", False))
class PaginationDescriptor(Descriptor):
    def __init__(self, value=False, **kwargs):
        self.value = value
        if not self.value:
            return

        self.items_per_page = kwargs["items_per_page"]
        self.relative = kwargs["relative"]
        self.always = kwargs["always"]
        super().__init__()


@fields(("orders", dict), ("multiple", False), ("always", False))
class OrderDescriptor(DictDescriptor):
    def __init__(self, value=False, **kwargs):
        self.value = bool(value and kwargs.get("fields"))
        if not self.value:
            return

        self.multiple = kwargs["multiple"]
        self.always = kwargs["always"]
        self.orders = self.dict = OrderedDict(
            (field[0], OrderDescriptorElement(
                field=field[0], type=field[1]
            )) for field in kwargs["fields"]
        )


@fields(("filters", dict), ("multiple", False), ("always", False))
class FilterDescriptor(DictDescriptor):
    def __init__(self, value=False, **kwargs):
        self.value = bool(value and kwargs.get("fields"))
        self.filters = self.dict = OrderedDict()
        self.multiple = False
        self.always = False
        if not self.value:
            return

        self.multiple = kwargs["multiple"]
        self.always = kwargs["always"]
        self.filters = self.dict = OrderedDict(
            (field[0], FilterDescriptorElement(
                field=field[0], operations=field[1]
            )) for field in kwargs["fields"]
        )
        super().__init__()


@fields(("always", False))
class CountDescriptor(Descriptor):
    def __init__(self, value=False, **kwargs):
        self.value = value
        if not self.value:
            return
        self.always = kwargs["always"]
        super().__init__()


@fields(("always", False), ("fields", list))
class SpecificDescriptor(Descriptor):
    def __init__(self, value=False, **kwargs):
        self.value = value
        if not self.value:
            return
        self.fields = kwargs["fields"]
        self.always = kwargs["always"]
        super().__init__()


@fields(("always", False))
class RangeDescriptor(Descriptor):
    def __init__(self, value=False, **kwargs):
        self.value = value
        if not self.value:
            return
        self.always = kwargs["always"]
        super().__init__()


@fields("field", "type")
class OrderDescriptorElement:
    def __init__(self, field, type):
        if not isinstance(field, str):
            raise TypeError("field must be a string.")
        if not isinstance(type, Order):
            raise TypeError("type must be of type Order.")
        self.field = field
        self.type = type


@fields("field", "operation")
class FilterDescriptorElement:
    def __init__(self, field, operations):
        if not isinstance(field, str):
            raise TypeError("field must be a string.")

        if isinstance(operations, str):
            operations = {operations}
        operations = set(operations)
        for op in operations:
            if op not in OPERATORS:
                raise TypeError("Operation '{}' is not valid.".format(op))

        self.field = field
        self.operations = operations


class CreateDescriptor(Descriptor):
    def __init__(self, value=False):
        self.value = value
        super().__init__()


class DeleteDescriptor(Descriptor):
    def __init__(self, value=False):
        self.value = value
        super().__init__()


@fields(("fields", list), ("multiple", False))
class UpdateDescriptor(Descriptor):
    def __init__(self, value=False, **kwargs):
        self.value = bool(value and kwargs.get("fields"))
        if not self.value:
            return

        self.fields = kwargs["fields"]
        self.multiple = kwargs["multiple"]
        super().__init__()


def all_objects(func=None):
    def decorator(func):
        func._query = True
        if not hasattr(func, "_decorators"):
            func._decorators = set()
        return func
    if func is not None:
        return decorator(func)
    return decorator


def _db_method_decorator(name):
    def metadecorator(decorator):
        def new_decorator(func):
            if hasattr(func, "_" + name):
                raise RuntimeError("Cannot use @{} twice.".format(name))
            all_objects(func)
            setattr(func, "_" + name, decorator())
            func._decorators.add(name)
            return func
        return new_decorator
    return metadecorator


def paginated(items_per_page=None, *, relative=False, always=True):
    if items_per_page is None and not relative:
        raise ValueError(
            "Either items_per_page must be specified or "
            "relative must be true.",
        )
    if items_per_page is not None and relative:
        raise ValueError(
            "relative cannot be true when items_per_page is given.",
        )

    @_db_method_decorator("paginated")
    def decorator():
        return PaginationDescriptor(
            True, items_per_page=items_per_page, relative=relative,
            always=always,
        )
    return decorator


def ordered_by(field_order_pair, *, multiple=False, always=True):
    if multiple and always:
        raise ValueError("multiple cannot be true when always is true.")
    field = field_order_pair
    fields = [field] if isinstance(field, tuple) else field

    @_db_method_decorator("ordered_by")
    def decorator():
        return OrderDescriptor(
            True, fields=fields, multiple=multiple, always=always,
        )
    return decorator


def filtered_by(field_op_pair, *, multiple=False, always=True):
    if multiple and always:
        raise ValueError("multiple cannot be true when always is true.")
    field = field_op_pair
    fields = [field] if isinstance(field, tuple) else field

    @_db_method_decorator("filtered_by")
    def decorator():
        return FilterDescriptor(
            True, fields=fields, multiple=multiple, always=always,
        )
    return decorator


def count(func=None, *, always=True):
    @_db_method_decorator("count")
    def decorator():
        return CountDescriptor(True, always=always)

    if func is not None:
        return decorator()
    return decorator


def ranged(func=None, *, always=True):
    @_db_method_decorator("ranged")
    def decorator():
        return RangeDescriptor(True, always=always)

    if func is not None:
        return decorator()
    return decorator


def specific(field, *, always=True):
    fields = [field] if isinstance(field, str) else field

    @_db_method_decorator("specific")
    def decorator():
        return SpecificDescriptor(fields=fields, always=always)
    return decorator


def create(func=None):
    @_db_method_decorator("create")
    def decorator():
        return CreateDescriptor(True)

    if func is not None:
        return decorator()
    return decorator


def delete(func=None):
    @_db_method_decorator("delete")
    def decorator():
        return DeleteDescriptor(True)

    if func is not None:
        return decorator()
    return decorator


def update(field, *, multiple=False):
    fields = [field] if isinstance(field, str) else field

    @_db_method_decorator("update")
    def decorator():
        return UpdateDescriptor(True, fields=fields, multiple=multiple)
    return decorator


@unique
class OpCompat(Enum):
    FULL = 1
    PARTIAL = 2
    NONE = 3


def op_compat(operation, supported_operations):
    supported = set(supported_operations)
    if operation in supported:
        return OpCompat.FULL
    if operation == ">" and ">=" in supported:
        return OpCompat.PARTIAL
    if operation == "<" and "<=" in supported:
        return OpCompat.PARTIAL
    return OpCompat.NONE


def merge_filters(filter1, filter2):
    if filter1.value != filter2.value:
        return None

    op1, op2 = filter1.operation, filter2.operation
    if op2 == "!=":
        op1, op2 = op2, op1
        filter1, filter2 = filter2, filter1
    elif op1 != "!=":
        return None

    if op2 in {">=", "<="}:
        return filter2._replace(operation=op2[:1])
    return None


def filter_objects(objects, filters):
    results = []
    for obj in objects:
        for filt in filters:
            operator_ = OPERATORS[filt.operation]
            if not operator_(getattr(obj, filt.field), filt.value):
                break
        else:
            results.append(obj)
    return results


def order_objects(objects, orders):
    def compare(obj1, obj2):
        for order in orders:
            f1 = getattr(obj1, order.field)
            f2 = getattr(obj2, order.field)
            if order.type == Order.ANY:
                raise TypeError("QueryOrderElement type cannot be ANY.")
            if f1 < f2:
                return -1 if order.type == Order.ASCENDING else 1
            if f1 > f2:
                return 1 if order.type == Order.ASCENDING else -1
        return 0
    return list(sorted(objects, key=compare))


def specific_object(objects, specific):
    for obj in objects:
        if getattr(obj, specific.field) == specific.value:
            return obj
    return None


class QueryFilterElement(
        namedtuple("QueryFilterElement", ["field", "operation", "value"])):
    def __new__(cls, *, field, operation, value):
        if not isinstance(field, str):
            raise TypeError("field must be a string.")
        if operation not in OPERATORS:
            raise ValueError("operation is not valid.")
        return super().__new__(
            cls, field=field, operation=operation, value=value
        )


class QueryOrderElement(
        namedtuple("QueryOrderElement", ["field", "type"])):
    def __new__(cls, *, field, type):
        if not isinstance(field, str):
            raise TypeError("field must be a string.")
        if not isinstance(type, Order):
            raise TypeError("type must be of type Order.")
        return super().__new__(cls, field=field, type=type)


class QuerySpecific(
        namedtuple("QuerySpecific", ["field", "value"])):
    def __new__(cls, *, field, value):
        if not isinstance(field, str):
            raise TypeError("field must be a string.")
        if not isinstance(value, bool):
            raise TypeError("value must be a bool.")
        return super().__new__(cls, field=field, value=value)


class QueryUpdateElement(
        namedtuple("QueryUpdateElement", ["field", "value"])):
    def __new__(cls, *, field, value):
        if not isinstance(field, str):
            raise TypeError("field must be a string.")
        return super().__new__(cls, field=field, value=value)


class CachedResult(namedtuple("CachedResult", ["objects", "params"])):
    def __new__(cls, *, objects, params, time=None):
        return super().__new__(cls, objects=objects, params=params)


class QueryParams(
        namedtuple("QueryParams", [
            "filters", "order", "range", "specific", "count",
        ])):
    def __new__(cls, *, filters, order, **kwargs):
        if not isinstance(order, tuple):
            order = tuple(order)

        # O(nm) where n is the number of filters and m is the number of filters
        # for each field, but m is probably very small (usually 1).
        filter_dict = defaultdict(list)
        for filt in filters:
            filter_list = filter_dict[filt.field]
            for i, other in enumerate(filter_list):
                merged = merge_filters(filt, other)
                if merged is not None:
                    filter_list[i] = merged
                    break
            else:  # Could not merge any two filters
                filter_list.append(filt)

        filters = set()
        for filter_list in filter_dict.values():
            filters |= set(filter_list)
        filters = frozenset(filters)
        return super().__new__(cls, filters=filters, order=order, **kwargs)

    @classmethod
    def _make(cls, iterable):
        return cls(**dict(zip(cls._fields, iterable)))

    def combine(self, other):
        return type(self)(
            filters=self.filters | other.filters,
            order=self.order or other.order,
            range=self.range or other.range,
            specific=self.specific or other.specific,
            count=self.count or other.count,
        )


# TODO
class PublicQuery:
    def __init__(self, query):
        self._query = query

    # TODO
    def filter(self, **kwargs):
        pass

    def order_by(self, *fields):
        fields = [
            f for f in (fields if isinstance(f, tuple) else (f, Order.ASCENDING))
        ]

        new = self._copy()
        for field, order in fields:
            new._query.order_dict[field] = QueryOrderElement(
                field=field, type=order,
            )
        return new

    def _copy(self):
        return type(self)(self._query)


class Query:
    def __init__(self, database):
        self.database = database
        self.order_dict = OrderedDict()
        self._filter_dict = {}
        self._range = None
        self._specific = None
        self.count = False

    def copy(self):
        obj = type(self)(self.database)
        for field in ["order_dict", "filter_dict"]:
            attr_val = getattr(obj, field)
            setattr(obj, field, type(attr_val)(attr_val))
        return obj

    @property
    def filter_dict(self):
        if self.specific:
            filt = QueryFilterElement(
                field=self.specific.field, operation="==",
                value=self.specific.value,
            )
            return {self.specific.field: filt}
        return self._filter_dict

    @filter_dict.setter
    def filter_dict(self, value):
        self._filter_dict = value

    @property
    def range(self):
        if self._specific:
            return range(1)
        return self._range

    @range.setter
    def range(self, value):
        self._range = value

    @property
    def specific(self):
        return self._specific

    @specific.setter
    def specific(self, value):
        self._specific = value

    def query_params(self, stats):
        method = stats.method
        filters = []
        missing_filters = self.missing_filters(
            method, executable=filters,
        )

        params = QueryParams(
            filters=filters, order=list(self.order_dict.values()),
            range=self.range, specific=self.specific, count=self.count,
        )
        post_params = QueryParams(
            filters=missing_filters, order=[], range=None,
            specific=None, count=False,
        )

        replacements = {}
        post_replacements = {}

        if not stats.correct_order:
            post_replacements["order"] = params.order
            replacements["order"] = []

        if not stats.usable_range:
            post_replacements["range"] = params.range
            replacements["range"] = None

        if not stats.usable_specific:
            post_replacements["specific"] = params.specific
            replacements["specific"] = None

        if not stats.usable_count:
            post_replacements["count"] = params.count
            replacements["count"] = False

        params = params._replace(**replacements)
        post_params = post_params._replace(**post_replacements)
        return params, post_params

    # Executes this query with the given method (and statistics).
    def execute(self, stats):
        params, post_params = self.query_params(stats)
        post_filts = []
        if stats.method.paginate.always:
            params, post_params, post_filts = self.get_pagination_params(
                params, post_params,
            )

        combined_params = params.combine(post_params)
        objects = self.database.get_cached(combined_params)
        if objects is not None:
            return objects
        objects = self.database.get_cached(params)
        if objects is not None:
            return self.post_process(objects, post_params, combined_params)

        objects = (
            self.exec_paginated(stats, params, post_filts)
            if stats.method.paginate.always
            else self.exec_normal(stats, params)
        )

        model_cls = self.database.model
        for obj in objects:
            if not isinstance(obj, model_cls):
                raise TypeError(
                    "Database method returned an object that is not an "
                    "instance of the model class '{}': {!r}".format(
                        model_cls.__name__, obj
                    )
                )
            obj.manager = model_cls.objects(self.database.id)

        self.database.add_to_cache(CachedResult(
            objects=objects, params=params,
        ))
        return self.post_process(objects, post_params, combined_params)

    def get_pagination_params(self, params, post_params):
        post_filts = []
        new_params = params
        new_post_params = post_params

        if params.range is not None:
            post_filts = post_params.filters
            new_post_params = new_post_params._replace(filters=frozenset())

        new_filters = new_params.filters | post_filts
        new_params = new_params._replace(filters=new_filters)
        return new_params, new_post_params, post_filts

    def exec_paginated(self, stats, params, post_filts):
        return self.depaginate(
            stats.method, range_=params.range, kwargs=dict(
                filters=params.filters, order=params.order,
            ), post_filts=post_filts,
        )

    def exec_normal(self, stats, params):
        return stats.method(
            filters=params.filters, order=params.order,
            range_=params.range, specific=params.specific,
            count=params.count,
        )

    def post_process(self, objects, post_params, combined_params=None):
        any_post = (
            post_params.specific or
            post_params.count or
            post_params.filters or
            post_params.order or
            post_params.range is not None
        )

        if not any_post:
            return objects
        if post_params.specific:
            return (objects or [None])[0]
        if post_params.count:
            return len(objects)
        if post_params.filters:
            objects = filter_objects(objects, post_params.filters)
        if post_params.order:
            objects = order_objects(objects, post_params.order)
        if post_params.range is not None:
            start, stop = post_params.range.start, post_params.range.stop
            objects = objects[start:stop]
        if combined_params is not None:
            self.database.add_to_cache(CachedResult(
                objects=objects, params=combined_params,
            ))
        return objects

    # Depaginates a paginated method.
    # Note: While it is not possible for this method to return duplicated items
    # (given unique IDs), it is possible for this method to skip items.
    def depaginate(self, method, range_, kwargs, post_filts):
        page = 0
        after = None
        num_skipped = 0
        results = []
        start = length = None
        if range_ is not None:
            start, stop = range_.start, range_.stop
            length = stop - start
        seen_ids = set()

        if not (start is None or method.paginate.relative or post_filts):
            num_per_page = method.paginate.num_per_page
            page = start // num_per_page
            num_skipped = page * num_per_page

        while length is None or len(results) < length:
            if method.paginate.relative:
                objects = method(after=after, **kwargs)
            else:
                objects = method(page=page, **kwargs)
            if not objects:
                return results

            after = objects[-1].id
            filtered = filter_objects(objects, post_filts)
            filtered = [obj for obj in filtered if obj.id not in seen_ids]
            seen_ids |= set(obj.id for obj in filtered)
            if start is not None and num_skipped < start:
                num_skipped += len(filtered[:start - num_skipped])
                filtered = filtered[start - num_skipped:]
            results += filtered
        return results

    # Gets the statistics (and method) best suited for this query.
    def best_method_stats(self):
        methods = self.database.methods
        compatible = []

        for method in methods:
            if self.compatible_method(method):
                compatible.append(method)

        stats = list(map(self.method_stats, compatible))
        if not stats:
            raise RuntimeError("No compatible database method found.")
        best_stats = max(stats, key=cmp_to_key(compare_stats))
        return best_stats

    # Checks whether the given method can be used for this query.
    def compatible_method(self, method):
        if method.create or method.delete or method.update:
            return False
        if method.count.always and not self.count:
            return False
        if method.specific.always and not self.specific:
            return False

        if method.filters.always:
            for filt in method.filters.values():
                if filt.field not in self.filter_dict:
                    return False
                op = self.filter_dict[filt.field].operation
                if op_compat(op, filt.operations) == OpCompat.NONE:
                    return False

        if method.count.always and any(self.missing_filters(method)):
            return False
        return True

    # Gets statistics for the given method.
    def method_stats(self, method):
        print(method.func)
        print("mfilts:", list(self.missing_filters(method)))
        num_missing_filters = len(list(self.missing_filters(method)))
        correct_order = self.has_correct_order(method)
        usable_range = (
            self.range is not None and
            num_missing_filters == 0 and correct_order
        )

        correct_range = usable_range and (
            (self.range is not None and method.range) or
            (self.range is None and not (method.range or method.paginate))
        )

        usable_specific = self.specific and self.specific in method.specific
        usable_count = self.count and num_missing_filters == 0
        return MethodStats(
            method,
            num_missing_filters=num_missing_filters,
            correct_order=correct_order,
            correct_range=correct_range,
            usable_range=usable_range,
            usable_specific=usable_specific,
            usable_count=usable_count,
        )

    # Finds filters that the given method will not perform, optionally
    # also returning the filters that it will execute.
    def missing_filters(self, method, executable=None):
        return list(self._missing_filters(method, executable))

    def _missing_filters(self, method, executable):
        only_one_exec = not (method.filters.always or method.filters.multiple)
        any_executable = False
        for filt in self.filter_dict.values():
            if any_executable and only_one_exec:
                yield filt
                continue
            method_filt = method.filters.get(filt.field)
            if method_filt is None:
                yield filt
                continue
            compat = op_compat(filt.operation, method_filt.operations)
            if compat == OpCompat.NONE:
                yield filt
                continue
            if compat == OpCompat.PARTIAL:
                new_op = {">": ">=", "<": "<="}[filt.operation]
                filt = QueryFilterElement(
                    field=filt.field, operation=new_op, value=filt.value,
                )
                yield QueryFilterElement(
                    field=filt.field, operation="!=", value=filt.value,
                )
            if executable is not None:
                executable.append(filt)
                any_executable = True

    # Checks whether the given method will return objects in the correct order.
    def has_correct_order(self, method):
        if method.order.always:
            if len(self.order_dict) > len(method.order):
                return False

            order_pairs = zip(self.order_dict.values(), method.order.values())
            for order, method_order in order_pairs:
                if method_order.field != order.field:
                    return False
                if method_order.type == Order.ANY:
                    continue
                if order.type != method_order.type:
                    return False
            return True

        if method.order.multiple or len(self.order_dict) <= 1:
            for order in self.order_dict.values():
                method_order = method.order.get(order.field)
                if method_order is None:
                    return False
                if method_order.type == Order.ANY:
                    continue
                if order.type != method_order.type:
                    return False
            return True
        return False


# Chooses the preferred method for execution.
def compare_stats(stats1, stats2):
    method1, method2 = stats1.method, stats2.method
    if stats1.usable_specific != stats2.usable_specific:
        return 1 if stats1.usable_specific else -1

    if stats1.usable_count != stats2.usable_count:
        return 1 if stats1.usable_count else -1

    if stats1.correct_range != stats2.correct_range:
        return 1 if stats1.correct_range else -1

    if stats1.usable_range != stats2.usable_range:
        return 1 if stats1.usable_range else -1

    method1_all = not (method1.range or method1.paginate)
    method2_all = not (method2.range or method2.paginate)
    if method1_all != method2_all:
        return (
            (-1 if method1_all else 1) *
            (1 if stats1.usable_range else -1)
        )

    if stats1.num_missing_filters != stats2.num_missing_filters:
        return (
            1 if stats1.num_missing_filters < stats2.num_missing_filters
            else -1
        )

    if not method1_all and method1.range != method2.range:
        return 1 if method1.range else -1

    if stats1.correct_order != stats2.correct_order:
        return 1 if stats1.correct_order else -1
    return 0
